1. Technical Field of the Invention
The present invention relates to computer-aided design (CAD) and, more particularly, to regularity extraction in the design of integrated circuits.
2. Background Art
In high-performance custom integrated circuit designs, designers take advantage of the high degree of regularity often present in circuits to generate efficient layouts in terms of area and performance as well as to reduce the design effort. Datapath circuits perform various arithmetic and multiplexing operations on wide buses. Such circuits have a very high degree of regularity. The design effort can be reduced by identifying or extracting regularity in circuits, thus improving the productivity of designers. Currently, however, datapath circuits in general-purpose microprocessors are designed almost entirely by hand. Existing CAD tools can not extract and utilize regularity to the extent necessary for competitive designs.
Various techniques for extraction of functional regularity have been proposed in the literature. For example, D. S. Rao et al., xe2x80x9cOn clustering for maximal regularity extraction,xe2x80x9d IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 12, No. 8 (August. 1993), pp. 1198-1208, describes a string matching algorithm to find all instances of user-specified templates in the circuit, and then heuristically choose a subset of the set of templates to cover the circuit. The final cover is sensitive to the templates provided by the designer. M. R. Corazao et al., xe2x80x9cPerformance optimization using template mapping for datapath-intensive high-level synthesis,xe2x80x9d IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 15, No. 8 (August 1996), pp. 877-887, also assumes that a template library is provided, but claims to generate all complete as well as partial instances of a given template in the circuit. Another approach described in R. X. T. Nijssen et. al., xe2x80x9cRegular layout generation of logically optimized datapaths,xe2x80x9d Proc. Int""l Symp. on Physical Design, (1997), pp. 42-47, involves choosing small logic components, such as latches, as templates, and then growing them to obtain bigger templates. This approach is highly dependent on the initial choice of templates.
Various techniques for extraction of structural regularity have also been proposed in the literature. For example, G. Odawara et al., xe2x80x9cPartitioning and Placement Technique for CMOS Gate Arrays,xe2x80x9d IEEE Trans. on CAD, Vol. 6, No. 3 (May 1987), pp. 355-363, presents a methodology to identify structural regularity in highly-regular datapaths. Odawara""s method chooses latches driven by the same control signals as initial templates, and uses them to grow larger templates. Odawara""s approach identifies one-dimensional regularity in terms of bit-slices of the datapath. Other approaches by R. X. T. Nijssen et al, xe2x80x9cRegular Layout Generation of Logically Optimized Datapaths,xe2x80x9d Proc. Int""s Symp. on Physical Design, (1997) pp. 42-47, and S. R. Arikati et al., xe2x80x9cA Signature Based Approach to Regularity Extraction,xe2x80x9d Proc. Int""l Conf. on CAD, (Nov. 1997), pp. 542-545, extend Odawara""s methodology to identify bit slices as well as stages of datapath circuits. However, these structural methods are not sufficient for circuits with a mix of datapath and control logic.
In the approaches in the above-listed articles opportunities for regularity extraction are missed. Furthermore, there is a need for a regularity extraction approach which would speed up technology mapping and layout generation of datapath circuits without comprising the final design quality.
Accordingly, there is a need for techniques for systematic regularity extraction.
In some embodiments, the invention includes a computerized method for identifying structural regularity in a logic design. The method includes receiving a plurality of templates covering the logic design, receiving one or more control signals for the logic design, and receiving one or more databus identifiers for the logic design. The method generates a first vector for the logic design through computer automated operations to combine at least one instance of one of the plurality of templates based on the control signals, the databus identifiers and connectivity of the logic design.